package com.me.study.arithmeticAndDataStructure.dynamicProgramming;

import java.util.ArrayList;
import java.util.List;

/**
 * 动态规划: 求路径上的最大值
 *
 * @author ME
 * @date   2019/12/9
 */
public class DynamicProgramming {

    /**计算到当前点时的最大值*/
    private int[][] best = null;
    /**行数*/
    private int Y = 0;
    /**列数*/
    private int X = 0;

    // 定义方向常量
    private static final int RIGHT = 1;
    private static final int DOWN = 2;
    // 存储最好路径
    private List<Integer> bestPath = null;

    // 计算best(i,j)
    private void calcDp(int[][] matrix) {
        // 初始化
        Y = matrix.length;
        X = matrix[0].length;
        best = new int[Y][X];

        /*
         * { 300, 500, 560, 400, 160},
         * {1000, 100, 200, 340, 690},
         * { 600, 500, 500, 460, 320},
         * { 300, 400, 250, 210, 760}
         */
        // 计算
        for(int i = 0; i < Y; i++) {
            for(int j = 0; j < X; j++) {
                // 边界
                if(i == 0 && j == 0) {
                    best[i][j] = matrix[i][j];
                } else if(i == 0) {
                    best[i][j] = best[i][j - 1] + matrix[i][j];
                } else if(j == 0) {
                    best[i][j] = best[i - 1][j] + matrix[i][j];
                } else {
                    // 状态转移
                    best[i][j] = Math.max(best[i - 1][j], best[i][j - 1]) + matrix[i][j];
                }
            }
        }
    }

    // 获取最大值
    public int getMaxAward(int[][] matrix) {
        // 计算状态
        calcDp(matrix);
        // 计算最佳路径
        calcBestPath();
        // 返回最大值
        return best[matrix.length - 1][matrix[0].length - 1];
    }

    // 计算最佳路径，从后往前
    private void calcBestPath() {
        bestPath = new ArrayList<>();
        // 总共走 Y + X - 2 步
        int curY = Y - 1;
        int curX = X - 1;
        // 根据best(i,j)计算最佳路径
        for(int i = 0; i < Y + X - 2; i++) {
            if(curY == 0) {
                curX--;
                bestPath.add(RIGHT);
            } else if(curX == 0) {
                curY--;
                bestPath.add(DOWN);
            } else {
                if(best[curY - 1][curX] > best[curY][curX - 1]) {
                    curY--;
                    bestPath.add(DOWN);
                } else {
                    curX--;
                    bestPath.add(RIGHT);
                }
            }
        }
    }

    // 打印最佳路径
    public void printBestPath() {
        // 倒序打印
        for(int i = bestPath.size() - 1; i >= 0; i--) {
            if(bestPath.get(i) == RIGHT) {
                System.out.print("右 ");
            } else {
                System.out.print("下 ");
            }
        }
        System.out.println();
    }
    
}
